package com.sali.回溯算法;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 给定一个字符串 s ，返回 其重新排列组合后可能构成的所有回文字符串，并去除重复的组合 。
 * <p>
 * 你可以按 任意顺序 返回答案。如果 s 不能形成任何回文排列时，则返回一个空列表。
 */
public class LeetCode_267 {

    public static void main(String[] args) {
        String s = "aabbcc";
        List<String> strings = generatePalindromes(s);
        for (String str : strings) {
            System.out.print(str + " ");
        }
    }

    public static List<String> generatePalindromes(String s) {
        List<String> res = new ArrayList<>();

        // 统计s中一半的那些字符
        Map<Character, Integer> map = new HashMap<>();
        for (char ch : s.toCharArray()) {
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }

        Character midCh = null;
        int count = 0;
        for (Character ch : map.keySet()) {
            if (map.get(ch) % 2 == 1) {
                midCh = ch;
                count += 1;
                map.put(ch, map.get(ch) - 1);
            }
        }

        if (count > 1) {
            return res;
        }

        List<Character> chs = new ArrayList<>();
        for (Character key : map.keySet()) {
            for (int i = 0; i < map.get(key) / 2; i++) {
                chs.add(key);
            }
        }

        boolean[] visited = new boolean[chs.size()];
        getRes(chs, new StringBuilder(), res, visited, midCh);

        return res;
    }

    private static void getRes(List<Character> chs, StringBuilder sb, List<String> res, boolean[] visited, Character midCh) {
        if (sb.toString().length() == chs.size()) {
            if (midCh == null) {
                String str1 = new StringBuilder(sb).reverse().toString() + new StringBuilder(sb).toString();
                res.add(str1);
            } else {
                String str1 = new StringBuilder(sb).reverse().toString() + midCh + new StringBuilder(sb).toString();
                res.add(str1);
            }
            return;
        }

        for (int i = 0; i < chs.size(); i++) {
            if (visited[i]) {
                continue;
            }
            if (i > 0 && chs.get(i) == chs.get(i - 1) && !visited[i - 1]) {
                continue;
            }
            visited[i] = true;
            sb.append(chs.get(i));
            getRes(chs, sb, res, visited, midCh);
            visited[i] = false;
            sb.deleteCharAt(sb.toString().length() - 1);
        }
    }

}
